package org.ghost.nlp.algorithm;

import org.ghost.nlp.model.DictModel;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Administrator
 * @date 2021-04-11 12:59
 */
public class MaximumMatching {
    private MaximumMatching() {
    }

    /**
     * 正向最大匹配
     */
    public static List<String> fmm(DictModel dictModel, String str) {
        List<String> results = new ArrayList<String>();
        String input = str;
        while (input.length() > 0) {
            // 每次取小于或者等于最大字典长度的子串进行匹配
            int len = Math.min(input.length(), dictModel.getMaxLen());
            String subSeq = input.substring(0, len);
            while (subSeq.length() > 0) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if (dictModel.getDict().contains(subSeq) || subSeq.length() == 1) {
                    results.add(subSeq);
                    // 输入中从前向后去掉已经匹配的子串
                    input = input.substring(subSeq.length());
                    break;
                } else {
                    // 去掉匹配字段最后面的一个字
                    subSeq = subSeq.substring(0, subSeq.length() - 1);
                }
            }
        }
        return results;
    }

    /**
     * 逆向最大匹配
     */
    public static List<String> rmm(DictModel dictModel, String str) {
        // 采用堆栈处理结果，后进先出
        Stack<String> store = new Stack<String>();
        String input = str;

        while (input.length() > 0) {
            String subSeq;
            // 每次取小于或者等于最大字典长度的子串进行匹配
            if (input.length() < dictModel.getMaxLen()) {
                subSeq = input;
            } else {
                subSeq = input.substring(input.length() - dictModel.getMaxLen());
            }
            while (subSeq.length() > 0) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if (dictModel.getDict().contains(subSeq) || subSeq.length() == 1) {
                    store.add(subSeq);
                    // 输入中从后向前去掉已经匹配的子串
                    input = input.substring(0, input.length() - subSeq.length());
                    break;
                } else {
                    // 去掉匹配字段最前面的一个字
                    subSeq = subSeq.substring(1);
                }
            }
        }
        // 输出结果
        List<String> results = new ArrayList<String>();
        int size = store.size();
        for (int i = 0; i < size; i++) {
            results.add(store.pop());
        }
        return results;
    }

    /**
     * 双向最大匹配
     */
    public static List<String> bmm(DictModel dictModel, String str) {
        List<String> leftMax = fmm(dictModel, str);
        List<String> rightMax = rmm(dictModel, str);

        // 如果分词的数量结果不同，返回长度较小的
        if (leftMax.size() != rightMax.size()) {
            if (leftMax.size() > rightMax.size()) {
                return rightMax;
            } else {
                return rightMax;
            }
        }
        // 如果分词的数量结果相同
        else {
            //计算各自的  单字数
            int leftSingle = 0, rightSingle = 0;
            boolean isEqual = true;
            for (int i = 0; i < rightMax.size(); i++) {
                if (!leftMax.get(i).equals(rightMax.get(i))) {
                    isEqual = false;
                }
                //判断是否为 单字
                if (leftMax.get(i).length() == 1) {
                    leftSingle++;
                }
                if (rightMax.get(i).length() == 1) {
                    rightSingle++;
                }
            }
            // 如果正向、逆向匹配结果完全相等，返回任意结果
            if (isEqual) {
                return leftMax;
                // 否则，返回单字数少的匹配方式
            } else if (leftSingle > rightSingle) {
                return rightMax;
            } else {
                return leftMax;
            }
        }
    }
}
